COMMENT ⊗   VALID 00003 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	However, this text is %2not%* meant to be a programming manual for LISP.
C00013 00003	This text is primarily designed for undergraduates and therefore
C00018 ENDMK
C⊗;
However, this text is %2not%* meant to be a programming manual for LISP.
A certain amount of time is spent giving insights into techniques for
writing LISP functions.  There are two reasons for this. First, the style
of LISP programming is quite different from that of "normal" programming.
LISP was one of the first languages to exploit the virtues of recursive
programming and explore the power of function-valued variables.
Second, and more important, we will spend a great deal of time discussing
various levels of implementation of the language. LISP is an excellent
medium for introducing standard techniques such as recursion, garbage collection,
storage allocation, and hashing. It is pointless to attempt discussing
the implementation of a language unless the reader has a through grasp of that
language.

If the only reasons for learning a programming language were its applications,
then for most standard applications we could do better than LISP.  LISP
is at least fifteen years old and many languages now offer themselves with better
notation, more efficient running code, or larger varieties of data structure.
But the more interesting aspects of LISP for students of Computer Science lie
not in its features as a programming language, but in what it can show
about the %2structure%* of Computer Science. The application of
computers, as is hardware development, is peripheral to this field. There is a
rapidly expanding body of knowledge unique to Computer Science, neither
mathematical nor engineering per se.  Much of this area is presented most
clearly by studying LISP.
As mentioned above, language implementors can learn much from LISP.  Indeed,
many of the "standard techniques" in language implementation (e.g. built-in
recursion, garbage collection) originated
with LISP. Many of the more theoretical areas of Computer Science 
(e.g. provability, semantics) can be
introduced using LISP. Many of the most interesting applications of computers
(e.g. artifical intelligence, game playing, theorem proving) 
have been done using LISP.

Much of the power of LISP lies in its simplicity.
The data structures are rich enough  to easily
describe sophisticated algorithms but not so rich as to become obfuscatory.
We will describe translators -- interpreters and compilers -- as very transparent
LISP functions.  Indeed the structure of the compilation process becomes so
transparent as to border on the trivial.  This is not to say that compiler writing
is trivial or even easy; but the structure of the process is easily seen.
This is partly due to the simplicity of the language, but perhaps more
due to our ability to go right to the compiling process without becoming
bogged down in details of scanners and parsers -- syntax--. Again, syntax
analysis is not trivial, but it is an activity only slightly
 germane to our understanding of compilers and evaluators.

LISP is a better vehicle than its ancestor, the λ-calculus, because there is just enough
more complexity present in LISP to make its implementation a realistic 
Computer Science task and not just
an interesting mathematical curiosity. Most every aspect of the implementation
of LISP and its translators has immediate implications to the implementation of 
other languages and to the design of programming languages in
general.
LISP has very important implications in the field of programming language
semantics, and  is the dominant language in the closely related study of
provability of properties of programs.

The idea of proving properties of programs hase been around for a very
long time. Goldstine and von Neumann were aware of the practical benefits
of such endeavors. J. McCarthy's work in LISP and the Theory of Computation
sought to establish formalisms and rules of inference for  reasoning
about programs.
However the  working programmers recognized debugging as the
only tool with which to generate a "correct" program, though  clearly
the non-occurence of bugs is no guarantee of correctness
⊗↓In truth, it usually meant that no one was using the program.←.
The sad state of affairs is that the programmer was right. Until
very recently techniques for establishing correctness of practical
programs simply did not exist.

A recent set of events is beginning to change this.

.BEGIN INDENT 0,10,10;
%21.%* Programs are becoming so large and complex that, even though
we write in a high-level language, our intuitions are not sufficient
to sustain us when we try to find bugs. We are literally being forced
to look beyond debugging.

%22.%* The formalisms are maturing. We know a lot more about how
to write "structured programs"; we know how to design languages
whose constructs are more amenable to proof techniques.
And most importantly, the tools we need for expressing properties of 
programs are finally being developed.

%23.%* The development of on-line techniques. The on-line system is
only reason that the traditional means construction and
modification of complex programs and systems has been able to survive 
this long. Sophisticated display editors, debuggers and file handlers
have kept us from falling over the edge. 
The use of these on-line devices in an interactive program constructing
system should allow us to actually  write  correct practical programs.

.END

This enlightened  view of programming  blends well with the LISP philosophy.
We  will show that the most natural way to write LISP programs
is "structured" in the best sense of the word, being  clean in
control structure, concise by not attempting to do too much,
and independent of a particular data representation.

Many of the existing techniques for establshing correctness originated
in McCarthy's investigations of LISP. And the very recent work of D. Scott
on mathematical models for programming languages are easily presented
in a discussion of LISP. These very mathematical studies are important.
Until we understand the objects of a discipline we cannot hope to
characterize the notion of a  convincing proof. The objects of
study here are programs (or functions).

Finally there are certain properties of LISP-like languages which
make them the natural candidate for  interactive program specification.
In the chapter on implications of LISP we will characterize "LISP-like"
and show how interactive methods can be developed.


This text is primarily designed for undergraduates and therefore
an attempt is made to make it self-contained. 
There are basically four areas in which to distribute the topics covered:
the mechanics of the language, the evaluation of expressions in LISP,
the static structure of LISP, and the dynamic structure of LISP. 
The first area develops  the programming philosophy of LISP: the use
data structures in programming; the language constructs of recursion and
other uncommon control structures.  Secondly, a careful study of the
meaning of evaluation in LISP gives insights into other languages and to the
general question of implementation. The last two areas are involved with
implementation. The section on static structure deals with the basic 
orgainzation of memory for a LISP machine#--#be it hardware or simulated
in software. The dynamics of LISP  discusses the primitive control structures
necessary for implementation of the LISP control structures, and procedure
calls. LISP compilers are discussed here.
Each area
builds on the previous. Taken as a group these topics introduce 
much of what is interesting Computer Science.

There is only one viable alternative to LISP if we wish to cover this broad
scope of topics in a unified approach: invent our own language. Other contemporary
languages lack some or all of the necessities.
Toy languages are suspect for several reasons. The student may suspect
(usually for good reason) that he is the subject in a not too clever
experiment being performed upon him by his instructor. 
Having a backlog of fifeen years in
experience and example programs should do much to subdue this discomfort.
The development of LISP also shows many of the mistakes 
⊗↓ah, the power of hindsight!←
that the original implementors and designers made.
However with these admonitions in mind we will try our hand at incorporating many
of the lessons learned from LISP and propose a possible
extension of LISP. This extension, described in {yonsec(P87)} 
is given not as a panacea
but rather as an example of how a careful study of LISP can aid in the 
design of a language.

A large collection of problems has been included. The reader is urged to do as
many as possible.  The problems are mostly non-trivial; they attempt to be
realistic, introducing some new information which the readers should be
able to discover themselves. 

There are also a few rather substantial projects.  At least one should be attempted.
There is a significant difference between being able to program small problems
 and handle large projects. The increase in difficulty is exponential
rather than linear.